package Offer.offer2017;

/**
 * 斐波拉契数列
 * Created by 雷文康 on 2017/12/29.
 */
public class Test09 {

    public static void main(String[] args) {
        long result = fibonacci(100);
        System.out.println(result);
    }

    /**
     * 循环法
     */
    public static long fibonacci(int n){
        if (n <= 0) {
            return 0;
        }
        if (n == 1){
            return 1;
        }
        long first = 0;
        long second = 1;
        long result = 0;
        for (int i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

    /**
     * 递归法
     * @param n
     * @return
     */
    public static long fibonacci2(int n) {
         if (n <=0 ) {
             return 0;
         }
         if (n == 1){
             return 1;
         }
         return fibonacci(n-2) + fibonacci(n-1);
    }
}
